package demo11;

import java.util.ArrayList;
import java.util.List;

public class Tree {
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode (char val){
            this.val=val;
            this.left=null;
            this.right=null;
        }
    }
    //创建树
    public TreeNode creat()
    {
        TreeNode node1=new TreeNode('A');
        TreeNode node2=new TreeNode('B');
        TreeNode node3=new TreeNode('C');
        TreeNode node4=new TreeNode('D');
        TreeNode node5=new TreeNode('E');
        TreeNode node6=new TreeNode('F');
        TreeNode node7=new TreeNode('G');
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        node3.right=node7;
        return node1;

    }
    //前序遍历
    public void prevnode(TreeNode head){
        if(head==null){
            return;
        }
        System.out.print(head.val+" ");
        prevnode(head.left);
        prevnode(head.right);
    }
    //中序遍历
    public void inorder(TreeNode head){
        if(head==null){
           return;
        }
        inorder(head.left);
        System.out.print(head.val+" ");
        inorder(head.right);
    }
    public  void pastorder(TreeNode head){
        if(head==null){
           return;
        }
        pastorder(head.left);
        pastorder(head.right);
        System.out.print(head.val+" ");
    }
    //第二种前序遍历
    List<Character> list=new ArrayList<>();
    public List<Character> pre(TreeNode head){
        if(head==null){
            return list;
        }
        list.add(head.val);
        pre(head.left);
        pre(head.right);
        return list;
    }
    //第三种前序遍历

    public List<Character> pre2(TreeNode head) {
        List<Character> list=new ArrayList<>();
        if(head==null){
            return list;
        }
        list.add(head.val);
        List<Character> list1=pre2(head.left);
        list.addAll(list1);
        List<Character> list3=pre2(head.right);
        list.addAll(list3);
        return list;
    }
    //二叉树获取结点个数第一种方法
    public static int size=0;
    public int size(TreeNode head){
        if(head==null){
            return 0;
        }
        size++;
        size(head.left);
        size(head.right);
        return size;
    }
    //二叉树获取结点个数第二种方法
    public int size1(TreeNode head){
        if(head==null){
            return 0;
        }
        return size1(head.left)+size1(head.right)+1;
    }
    //获取叶子结点个数
    public static int leafcount;
    public int getLeafNode(TreeNode head ){
        if(head==null){
            return 0;
        }
        if(head.left==null&&head.right==null){
            leafcount++;
        }
        getLeafNode(head.left);
        getLeafNode(head.right);
        return leafcount;
    }
    //获取第k层结点数=第k-1层左右子树的孩子节点个数
    public int getlevel(TreeNode head,int k){
        if(head==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
     return (getlevel(head.left,k-1)+   //向前走一步
        getlevel(head.right,k-1));
    }
    //求二叉树的高度=左树高度与右树高度的最大值+1
    public int getHeight(TreeNode head){
        if(head==null){
            return 0;
        }
        int leftHeight=getHeight(head.left);
        int rightHeight=getHeight(head.right);
        return Math.max(leftHeight,rightHeight)+1;
    }
    //检测value值是否存在，根节点不是的话找左边遇到null一层层找左子树的右边没有找右边
    public TreeNode findval(TreeNode head,char ch){
        if(head==null){
            return null;
        }
        if(head.val==ch){
            return head;
        }
        TreeNode left=findval(head.left,ch);
        if(left!=null){
            return left;
        }
        TreeNode right=findval(head.right,ch);
        if(right!=null){
            return right;
        }
        return null;
    }
    //判断两棵树的结构、节点值是否相同
    public boolean isSame(TreeNode p,TreeNode q){
        if(p!=null&&q==null||p==null&&q!=null){ //判结构
            return false;
        }
        if(p==null&&q==null){   //判结构
            return true;
        }
        if(q.val!= p.val){      //判节点值
            return false;
        }
        return isSame(p.left,q.left)&&isSame(p.right,q.right);
    }
    //两棵二叉树判断一棵二叉树中是否包括另一棵二叉树的某节点与这个节点的所有子树
    //方法是判断当前子树父节点是否与根节点一致或者与该子树与左子树相同或者该子树与右子树相同
    public boolean isSubtree(TreeNode head1,TreeNode head2){
        if(head1==null){
            return false;   //空树
        }
        if(isSame(head1,head2)){
            return true;
        }
        if(isSame(head1.left,head2)){       //判此树是否等于左子树
            return true;
        }
        if(isSame(head1.right,head2)){  //判此树是否等于右子树
            return true;
        }
        return false;
    }
    //翻转二叉树：每个节点左右相互交换
    public  TreeNode  inverTree(TreeNode head){
        if(head==null){
            return null;
        }
        if(head.left==null&&head.right==null){
            return head;
        }
        TreeNode tmp=head.left;
        head.left=head.right;
        head.right=tmp;
        inverTree(head.left);//左树
        inverTree(head.right);//右树
        return head;
    }

}
